package com.yc.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 链表
 */
public class LinkTest {
    public static void main(String[] args) {
        LinkTest t = new LinkTest();
//        t.m1();
//        t.m2();
//        t.m3();
        t.m4();
    }

    public void m1() {
//        ListNode a = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode a = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode res = oddEvenList(a);
        do {
            System.out.println(res.val);
            res = res.next;
        } while (res != null);
    }

    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        ListNode j = head;//奇数的尾
        ListNode o = head.next;//偶数的尾
        ListNode oo = head.next;//偶数的头
        ListNode index = head.next.next;
        oo.next = null;//必须保证偶数最后一定指向null，很重要，否则就死循环了
        int num = 2;
        while(index != null) {
            num++;
            if (num%2==1) {//奇数
                j.next = index;
                j = index;
                index = index.next;
//                j.next = null;//这句话之所以显示"'j.next' is never used"：是因为循环之外的第一句是j.next = oo;这句话直接作废（奇数末尾一定不为空）
            } else {
                o.next = index;
                o = index;
                index = index.next;
                o.next = null;//必须保证偶数最后一定指向null，很重要，否则就死循环了
            }

        }
        j.next = oo;
        return head;

    }

    public void m2() {
        ListNode a = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
//        ListNode a = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode res = reverseList(a);
        do {
            System.out.println(res.val);
            res = res.next;
        } while (res != null);
    }


    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode i = null;
        ListNode j = head;
        ListNode m = j;
        while (j != null) {
            m = m.next;
            j.next = i;
            i = j;
            j = m;
        }
        return i;

    }

    //反转链表
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) return head;
        // 解法一: 原地逆置
        // ListNode p = head, pre = null;
        // while (p != null) {
        //     ListNode next = p.next;
        //     p.next = pre;
        //     pre = p;
        //     p = next;
        // }
        // return pre;
        // 解法二: 头插法
        // ListNode dummyHead = new ListNode(-1, head);
        // ListNode pre = dummyHead, p = head;
        // while (p != null && p.next != null) {
        //     ListNode next = p.next;
        //     p.next = next.next;
        //     next.next = dummyHead.next;
        //     dummyHead.next = next;
        // }
        // return dummyHead.next;
        // 解法三: 递归
        // ListNode newHead = reverseList(head.next);
        // head.next.next = head;
        // head.next = null;
        // return newHead;
        // 解法四：尾递归
        return reverseTail(null, head);
    }
    public ListNode reverseTail(ListNode pre, ListNode p) {
        if (p == null) return pre;
        ListNode next = p.next;
        p.next = pre;
        return reverseTail(p, next);
    }


    public void m3() {
        TreeNode t = new TreeNode(10, new TreeNode(5, new TreeNode(3, new TreeNode(3), new TreeNode(-2)), new TreeNode(2, null, new TreeNode(1))), new TreeNode(-3, null, new TreeNode(11)));

//        System.out.println(pathSum(t, 8));
        System.out.println(pathSum2(t, 8));
    }

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        return getNum(root, targetSum, null);
    }

    int getNum(TreeNode node, int targetSum, int[] arr) {
        if (node == null) {
            return 0;
        }

        if (node.val > targetSum) {//本节点直接超：无论前面有没有传过来数组，都无效
            return getNum(node.left, targetSum, null) + getNum(node.right, targetSum, null);
        } else if (node.val == targetSum) {//本节点刚好：前面的数组失效
            return getNum(node.left, targetSum, null) +
                    getNum(node.right, targetSum, null) + 1;
        } else {//当前节点不够，看看有没有前面的节点加一加
            //计算加上本节点，是否能组成新的
            if (arr != null) {//不为空就一定有数据
                if (arr[arr.length-1] + node.val<=targetSum) {//有可能有符合的
                    boolean flag = false;
                    int i=arr.length-1;
                    while(i>=0) {
                        if (arr[i] + node.val == targetSum) {
                            arr[i] += node.val;//直接在原数组上改
                            flag = true;
                            break;//后面一旦有符合，前面就不用看了
                        }
                        i--;
                    }
                    if (flag) {//有符合的
                        if (i+1 == arr.length) {//就是最后一个
                            return getNum(node.left, targetSum, null) +
                                    getNum(node.right, targetSum, null) + 1;
                        } else {//把一部分复制出来
                            int[] nextArr = new int[arr.length-i];
                            System.arraycopy(arr,i=1,nextArr,0,arr.length-i-1);
                            nextArr[arr.length] = node.val;

                            int [] nextArr2 = new int[arr.length+1];
                            System.arraycopy(nextArr,0,nextArr2,0,nextArr.length);
                            return getNum(node.left, targetSum, nextArr) +
                                    getNum(node.right, targetSum, nextArr2) + 1;
                        }
                    } else {//没符合的：加上本节点，都太小
                        int[] nextArr = new int[arr.length+1];
                        System.arraycopy(arr,0,nextArr,0,arr.length);
                        nextArr[arr.length] = node.val;

                        int [] nextArr2 = new int[arr.length+1];
                        System.arraycopy(nextArr,0,nextArr2,0,nextArr.length);
                        return getNum(node.left, targetSum, nextArr) +
                                getNum(node.right, targetSum, nextArr2);
                    }
                } else {//加上本节点，都太大了:统统舍弃
                    return getNum(node.left, targetSum, null) +
                            getNum(node.right, targetSum, null);
                }

            } else {//前面没有
                int[] nextArr = {node.val};
                int[] nextArr2 = {node.val};
                return getNum(node.left, targetSum, nextArr) +
                        getNum(node.right, targetSum, nextArr2);
            }
        }


    }



    public int pathSum2(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }

    public void m4() {
//        ListNode t = new ListNode(5, new ListNode(4, new ListNode(2, new ListNode(1))));
        ListNode t = new ListNode(4, new ListNode(2, new ListNode(2, new ListNode(3))));
//        ListNode t = new ListNode(1, new ListNode(1000));
        System.out.println(pairSum2(t));
    }

    public int pairSum(ListNode head) {
        if (head == null) {
            return 0;
        }
        //快慢指针+栈
        ListNode s = head;
        ListNode f = head;
        List<Integer> list = new ArrayList<>();
        list.add(s.val);

        //
        while(f.next != null && f.next.next != null) {
            s = s.next;
            f = f.next.next;
            list.add(s.val);
        }
         s = s.next;//
        int max = 0;
        int len = list.size()-1;
        while(len>=0) {
            max = Math.max(list.get(len) + s.val, max);
            s = s.next;
            len--;
        }
        return max;

    }

    public int pairSum2(ListNode head) {
        if (head == null) {
            return 0;
        }
        //快慢指针+栈
        ListNode s = head;
        ListNode f = head;
        while(f.next.next != null) {
            s = s.next;
            f = f.next.next;
        }
        s = s.next;

        //翻转前半段
        ListNode cur = null;
        ListNode pre = head;
        ListNode tmp = pre;
        while(!pre.equals(s)) {
            tmp = tmp.next;
            pre.next = cur;
            cur = pre;
            pre = tmp;
        }

        //两个指针（cur，s）往两边迭代，找最大和
        int max = 0;
        //前半段: cur --> head 后半段：s --> f
        while(cur != null) {
            max = Math.max(max, cur.val + s.val);
            cur = cur.next;
            s = s.next;
        }

        return max;

    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}